package leet;

/**
 * 680. Valid Palindrome II
 * 
 * <pre>
 * Given a non-empty string s, you may delete at most one character. Judge
 * whether you can make it a palindrome.
 * </pre>
 * 
 * @author zhujunbing
 * @date 2019年4月25日
 */
public class Leet0680 {

	public static void main(String[] args) {
		Leet0680 leet0680 = new Leet0680();
		String s = "dee";
		boolean validPalindrome = leet0680.validPalindrome(s);
		System.out.println(validPalindrome);
	}

	public boolean validPalindrome(String s) {

		int length = s.length();
		char[] charArray = s.toCharArray();
		int head = 0;
		int tail = length - 1;
		while (head < tail) {

			if (charArray[head] == charArray[tail]) {
				head++;
				tail--;
			} else {

				if (tail - head == 1) {
					return true;
				}

				int head1 = head;
				int tail1 = tail - 1;
				boolean flag1 = true;
				while (head1 < tail1 && flag1) {
					if (charArray[head1] == charArray[tail1]) {
						head1++;
						tail1--;
					} else {
						flag1 = false;
					}
				}

				if (flag1) {
					return flag1;
				}
				int head2 = head + 1;
				int tail2 = tail;

				while (head2 < tail2) {
					if (charArray[head2] == charArray[tail2]) {
						head2++;
						tail2--;
					} else {
						return false;
					}
				}
				return true;
			}

		}

		return true;
	}
}
